# graph theory

graph theory
A branch of mathematics used to represent relations and networks. A graph consists of a set of points (nodes or vertices) and the pairwise links between them (arcs or lines). In sociological applications, the nodes are typically individuals, roles, or organizations, and the links are social relationships (such as kinship, friendship, communication, or authority). The links may take account of direction (a digraph) or ignore it (an undirected graph) and they may be at any level of measurement . Apart from the usual binary graph (where a link either exists or does not), special cases of interest include asymmetric graphs for representing tournaments, ordered graphs and lattices for organizational structures, trees for hierarchies and classification systems, signed (+, -) graphs for structural balance, real-valued graphs for distribution and assignment problems, and links which express the probability of a relationship (stochastic graphs).
Graph theory provides theorems (proved consequences) and algorithms (step-by-step procedures) used to obtain information, such as properties of individual points (popularity, centrality, liaison, or bridge status), of pairs (shortest path between two points) or subgroups (clique-detection, triads), and sub-graphs (blocks of points which are ‘structurally equivalent’ by having the same pattern of links).
Earliest sociological uses include sociometry and clique-detection, and more recently social network , kinship and citation structures, and ‘vacancy chains’ tracing the movement of occupational or housing vacancies through a system. Graph theory has also been extended to treat very large networks and to compare actual network structure with randomly constructed graphs.

Dictionary of sociology. 2013.

### Look at other dictionaries:

• Graph theory — In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and …   Wikipedia

• graph theory — Math. the branch of mathematics dealing with linear graphs. [1965 70] * * * Mathematical theory of networks. A graph consists of nodes (also called points or vertices) and edges (lines) connecting certain pairs of nodes. An edge that connects a… …   Universalium

• Glossary of graph theory — Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with… …   Wikipedia

• graph theory — noun Date: 1947 a branch of mathematics concerned with the study of graphs …   New Collegiate Dictionary

• graph theory — noun The study of the properties of graphs (in the sense of sets of vertices and sets of ordered or unordered pairs of vertices) …   Wiktionary

• graph theory — Math. the branch of mathematics dealing with linear graphs. [1965 70] …   Useful english dictionary

• Minor (graph theory) — In graph theory, an undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G. The theory of graph minors began with Wagner s theorem that a graph… …   Wikipedia

• List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 …   Wikipedia

• Connectivity (graph theory) — In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) which need to be removed to disconnect the remaining nodes from each other[1]. It is… …   Wikipedia

• Clique (graph theory) — A graph with 23 1 vertex cliques (its vertices), 42 2 vertex cliques (its edges), 19 3 vertex cliques (the light blue triangles), and 2 4 vertex cliques (dark blue). Six of the edges and 11 of the triangles form maximal cliques. The two dark blue …   Wikipedia

### Share the article and excerpts

##### Direct link
Do a right-click on the link above
and select “Copy Link”